package com.justnow.offer;

import com.sun.scenario.effect.impl.sw.java.JSWColorAdjustPeer;

import java.util.ArrayList;
import java.util.List;

/**
 * @author justnow
 * Created on 2020-09-21
 * Description
 *
 * 全排列方法二，基于交换的
 */
public class Leetcode46_Permute02 {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        dfs(0, nums);
        return res;
    }
    private void dfs(int x, int[] nums) {
        if (x == nums.length - 1) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            res.add(list);
            return;
        }

        for (int j = x; j < nums.length; j++) {
            swap(x, j, nums);
            dfs(x + 1, nums);
            swap(x, j, nums);
        }
    }

    private void swap(int a, int b, int[] nums) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public static void main(String[] args) {
        Leetcode46_Permute02 leetcode46_permute02 = new Leetcode46_Permute02();
        List<List<Integer>> permute = leetcode46_permute02.permute(new int[]{1, 2, 3});
        System.out.println(permute);
    }
}
